<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /* 
        单词重复使用，很明显的完全背包，而且单词是有序的，因此是排列。外层物品，内层背包

        背包容量为s，求是否能装满背包

        ①定义dp数组和下标含义
        dp[i]表示长度为i的字符串是否可以被拆分  
        
        ②状态转移方程
        如果字符串长度为j，重量为dp[wordDict[i].length]
        如果前一段字符为true，且剩余字符也在字典中，那么dp[j]=true
        j代表的是长度，因此剩余字符为s.slice(j-wordDict[i].length,j-1+1)

        ③初始化dp数组
        dp[0]=true

      */
      var wordBreak = function (s, wordDict) {
        let bagSize = s.length
        let dp = new Array(bagSize + 1).fill(false)
        dp[0] = true
        for (let j = 0; j <= bagSize; j++) {
          for (let i = 0; i < wordDict.length; i++) {
            if (j >= wordDict[i].length) {
              //注意：必须s.slice(j-wordDict[i].length)因为我们必须保证每次切掉的字符属于字典中的
              let temp = s.slice(j - wordDict[i].length, j)
              if (dp[j - wordDict[i].length] && wordDict.includes(temp)) {
                dp[j] = true
              }
            }
          }
        }
        return dp[bagSize]
      }
    </script>
  </body>
</html>
